package com.captjack.other;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Jack Sparrow
 * @version 1.0.0
 * @date 2022/10/17 00:01
 * package com.captjack
 */
public class Trie {

    private final TireNode root;

    public Trie() {
        root = new TireNode('#', false, new HashMap<>(30));
    }

    /**
     * insert
     *
     * @param word: a word
     */
    public void insert(String word) {
        // write your code here
        if (word == null || word.length() == 0) {
            return;
        }
        TireNode insert = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            //
            if (!insert.children.containsKey(currentChar)) {
                insert.children.put(currentChar, new TireNode(currentChar, false, new HashMap<>(30)));
            }
            insert = insert.children.get(currentChar);
        }
        insert.end = true;
    }

    /**
     * search
     *
     * @param word: A string
     * @return if the word is in the trie.
     */
    public boolean search(String word) {
        TireNode result = prefix(word);
        return result != null && result.end;
    }

    /**
     * startsWith
     *
     * @param prefix: A string
     * @return if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        // write your code here
        return prefix(prefix) != null;
    }

    /**
     * prefix
     *
     * @param prefix prefix
     * @return TireNode
     */
    private TireNode prefix(String prefix) {
        // write your code here
        if (prefix == null || prefix.length() == 0) {
            return null;
        }
        TireNode search = root;
        for (int i = 0; i < prefix.length(); i++) {
            char currentChar = prefix.charAt(i);
            //
            if (!search.children.containsKey(currentChar)) {
                return null;
            }
            search = search.children.get(currentChar);
        }
        return search;
    }

    /**
     * prefix
     *
     * @param prefix prefix
     * @return TireNode
     */
    public int maxMatch(String prefix) {
        // write your code here
        if (prefix == null || prefix.length() == 0) {
            return 0;
        }
        TireNode search = root;
        for (int i = 0; i < prefix.length(); i++) {
            char currentChar = prefix.charAt(i);
            //
            if (!search.children.containsKey(currentChar)) {
                return i;
            }
            search = search.children.get(currentChar);
        }
        return prefix.length();
    }

    private static class TireNode {

        private final Character val;

        private boolean end;

        private final Map<Character, TireNode> children;

        public TireNode(Character val, boolean end, Map<Character, TireNode> children) {
            this.val = val;
            this.end = end;
            this.children = children;
        }

    }

}

